#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e5 + 10;
vector<PII> edges[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;
const int INF = (1 << 31) - 1;
int n, m, s;
typedef long long LL;
LL dist[N];
bool st[N];
void dijkstra()
{
	for (int i = 0;i <= n;i++) dist[i] = INF;
	dist[s] = 0;
	heap.push({0,s});

	while (heap.size())
	{
		PII x = heap.top();heap.pop();
		int d = x.first;int y = x.second;
		if (st[y] == true) continue;
		st[y] = true;

		for (auto& e : edges[y])
		{
			int v = e.first;int w = e.second;

			if (dist[y] + w < dist[v])
			{
				dist[v] = dist[y] + w;
				heap.push({ dist[v], v });
			}
		}
	}
	for (int i = 1;i <= n;i++) cout << dist[i] << " ";
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1;i <= m;i++)
	{
		int u = 0, v = 0, w = 0;
		cin >> u >> v >> w;
		edges[u].push_back({ v,w });
	}

	dijkstra();
	return 0;
}